from base import *
# 关于回文串单链表：
## 1. 第一个知识点，链表同样具有递归的特性，可以把树结构理解为特殊的链表：
# 类似的，链表也可以有前序遍历、后续遍历，like this：
# 倒序打印单链表中的元素值
def traverse(head):
    if head is None:
        return
    # 在这里就是正序
    traverse(head.next)
    # 后序遍历代码
    print(head.val)

class Palindorme_Listnode(object):
    left=None
    res=True
    def solution(self,head):
        self.left=head
        self.transe_diff(head)
        return self.res
    def transe_diff(self,right):
        if right is None: # 递归必须有跳出条件，否则死循环
            return
        # 利用后续遍历，让右指针一路滑倒最右端
        self.transe_diff(right.next)
        if self.left.val!=right.val:
            self.res=False
            return
        self.left=self.left.next
    def test(self):
        head=list_2_ListNode([1,2,3,3,2,2,1])
        res=self.solution(head)
        print(res)

# 这个问题的剪枝优化是先找到链表的中点:
# todo: 暂略 优化：

if __name__=='__main__':
    Palindorme_Listnode().test()
